package datastructures;

import exceptions.EmptyListException;

/**
 * A PriorityQueue for storing {@link Waypoint}s in a simple linked List. 
 * 
 * @version 0.4.1
 * @since 0.4.0
 * @author Tim
 */
public class PriorityQueue {

	
	private PriorityNode head;
	
	
	/**
	 * Creates an empty {@link PriorityQueue}
	 */
	public PriorityQueue()
	{
		head = null;
	}
	
	/**
	 *   Stores the passed {@link Waypoint} in the {@link PriorityQueue}, ordered by the priority. A lower value means, 
	 *   that this object will be stored closer to the head. If the {@link Waypoint} is already stored in the {@link PriorityQueue}
	 *   the entry will be updated, if the priority of the passed {@link Waypoint} is lower than the existing one
	 *   
	 * @param wp The stored {@link Waypoint}
	 * @param priority Priority of the {@link Waypoint}. 
	 */
	public void insert(Waypoint wp, double priority)
	{
		if (head!=null)
		{
			boolean update = head.insert(priority, wp);
			if(update)
			{
				head = new PriorityNode(priority, wp, head);
				head.remove(wp);
			}
		}
		else
		{
			head = new PriorityNode(priority, wp);
		}
	}

	/**
	 * 
	 * @return Returns if the {@link PriorityQueue} is empty
	 */
	public boolean isEmpty()
	{
		return (head==null);
	}
	
	/**
	 * Returns and removes the first {@link Waypoint} of the {@link PriorityQueue}
	 * 
	 * @return The first {@link Waypoint} stored in this {@link PriorityQueue}
	 * @throws EmptyListException Is thrown, if the List is empty
	 */
	public Waypoint getFirst() throws EmptyListException
	{
		if (head!=null)
		{
			Waypoint item = this.head.getWaypoint();
			head = head.getNext();
			return item;
		}
		
		throw new EmptyListException("Die Liste ist leer");
	}
	
	/**
	 * Checks if the passed {@link Waypoint} is contained in this {@link PriorityQueue}
	 *  
	 * @param wp The {@link Waypoint} which is searched for
	 * @return True, if the {@link Waypoint} is contained, otherwise false 
	 */
	public boolean contains(Waypoint wp)
	{
		if (head==null)
		{
			return false;
		}
		return head.contains(wp);
	}
	
	/**
	 * Tries to remove the passed {@link Waypoint} from the {@link PriorityQueue} recursively
	 * 
	 * @param wp The {@link Waypoint} which should be removed
	 * @return True, if the {@link Waypoint} was removed 
	 * @throws EmptyListException 
	 */
	public boolean remove(Waypoint wp) throws EmptyListException
	{
		if (head==null)
		{
			throw new EmptyListException("The PriorityQueue is empty");
		}
		return head.remove(wp);
	}
	
	@Override
	public String toString() {
		String s = "Openlist:\n";
		PriorityNode n = head;
		while (n != null)
		{
			s += (n.toString()+"\n");
			n = n.getNext();
		}
		return s;
	}
	
}
